introduzione agli algoritmi e alle strutture dati

Oggi parleremo per me di uno degli argomenti più importanti nel mondo dell'informatica e di cui ogni persona che abbia fatto o no l'università deve avere almeno un infarinatura di base ovvero gli algoritmi e le strutture dati, oggi partiremo parlando delle strutture dati basilari e quelle che più vengono utilizzate e anche delle operazioni che è possibile fare su di loro:

• Array
• Set

Array:

Gli array sono la struttura dati più comunemente utilizzata in tutti i linguaggi di programmazione e ogni linguaggio di programmazione ha la propria implementazione di array per esempio in javascript gli array sono semplicemente gli array mentre in python gli array sono riconducibili alle liste e così via.

Io credo che chiunque stia leggendo questo articolo sappia almeno basilarmente cosa è un array, comunque per chi non lo sapesse l'array è una lista di elementi di dati ed è utile in molti casi per esempio mettiamo caso dobbiamo creare un applicazione per un azienda che vuole vendere i propri prodotti, l'array potrebbe essere utilizzato per rappresentare appunto la lista di oggetti da vendere e sarà formata in questo modo:

const array = ["elemento1","elemento2","elemento3","elemento4","elemento5"]; 

allora l'array come possiamo vedere ha 5 elementi, quindi diremmo che ha dimensione 5 poichè appunto ha 5 elementi, gli array hanno anche un indice che indica la posizione di un elemento all'interno di un array e se prima abbiamo detto che l'array è di dimensione 5, l'indice arriverà a 4 poichè gli array partono da 0, quindi il nostro elemento1 sarà l'elemento numero 0, quindi se noi vogliamo prendere un elemento da un array non diremmo prendimi il primo elemento ma diremmo prendimi l'elemento numero 0. Ovviamente ogni linguaggio di programmazione gestisce questa casistica a proprio modo, ma nella maggior parte dei casi troverete questo modo di gestire gli array.

I Set:

I set sono una struttura dati che non consente di avere duplicati al suo interno ed è questa la principale differenza rispetto ad un array cioè che il caso di utilizzo principale è quando hai bisogno di un qualcosa nel quale non possano essere inseriti doppioni come per esempio un elenco telefonico che non può contenere numeri uguali, però per avere questa funzione assai interessante di controllo dei duplicati dovremmo rinunciare un'pò alle prestazioni su alcune operazioni che vengono fatte sui set, ovviamente esistono diversi tipi di set oggi andremmo ad esplorare il set che si basa su un array, Rispetto a quello che vedrete qui sotto sulle operazioni sulle strutture dati, per i set possiamo considerare tutto valido solo l'inserimento cambia fra set e array e sotto vedrete le principali differenze.

Operazioni sulle strutture dati:

Le operazioni che è possibile fare su una struttura dati sono le seguenti:

Lettura:

La prima operazione che considereremo è quella di lettura, che ci permette di cercare i valori da dentro l'array a un determinato indice, questa è l'operazione più efficiente poichè il computer può leggere il valore dall'array in un solo passaggio ed è in grado di saltare da una cella all'altra appunto in un solo passaggio, ma vediamo come fa ad essere così efficiente questa operazione, per comprendere meglio pensiamo che il nostro computer abbia tante celle dove ogni cella rappresenta un indirizzo di memoria e dentro ogni indirizzo di memoria ci stanno i dati che il computer si salva per esempio mettiamo il caso che il computer voglia salvare un array da 5 elementi, cercherà in memoria 5 celle affiancate e le allocherebbe per contenere i dati dell’array e per poter accedere a questi dati tramite indice si salva l’indirizzo della cella di partenza dell’array e ci assegna il valore 0 e per trovare per esempio il valore al indice due andrà a sommare al indice di partenza, l’indice del valore che gli serve e così in un solo passaggio potrà accedere al valore che gli serve.

Ricerca:

La ricerca in un array significa verificare se un determinato valore è presente nell’array, la ricerca rispetto alla lettura è più inefficiente poichè la lettura impiega solo un passaggio per leggere il valore tramite un indice dato mentre per la ricerca noi diamo il valore e il computer nel migliore dei casi farà un solo passaggio se il valore si trova al primo indice, n passaggi se si trova al ultimo indice del array, diciamo che la ricerca è meno efficiente poichè il computer conosce l’indirizzo di memoria ma non sa che valore ci sia contenuto dentro inizialmente, questo tipo di ricerca molto basilare in cui si va alla ricerca del valore da noi indicato scorrendo valore per valore l’array viene chiamata “ricerca lineare” e si dice che per N elementi contenuti nel array ci saranno N passaggi svolti per cercare quell’elemento ovviamente nel caso peggiore cioè che l’elemento si trovi a fine array se no nel caso migliore ovvero che l’elemento che cerchiamo sta al primo indice, la ricerca avrebbe lo stesso numero di passaggi della lettura ovvero 1.

Inserimento In un array:

L’efficienza dell’inserimento di un nuovo dato in un array dipende da dove si sta inserendo il dato all’interno dell’array, se si sta inserendo il dato alla fine ci sarà bisogno di un solo passaggio, poichè il computer sa le dimensioni dell’array e l’indirizzo della cella di memoria da cui parte e quindi sarà semplice capire dove sia la fine per inserire l’elemento. Caso diverso se si deve inserire l’elemento al centro dell’array o proprio all’inizio poichè per inserire al inizio o in mezzo all’array dobbiamo prima spostare tutti gli elementi di una cella a destra e poi inserire l’elemento quindi nel caso peggiore avremmo che si faranno N+1 passaggi poichè si fanno N spostamenti e 1 inserimento.

Inserimento in un set:

L'inserimento in un set rispetto ad un array varia per il fatto che bisogna controllare anche se ci siano duplicati, lato prestazioni l'inserimento in un set nello scenario migliore richiede N+1 passaggi per N elementi, questo perchè sono necessari N passaggi per sapere se il valore che stiamo inserendo è realmente già presente nell'array e poi se non è già presente un altro valore allora il passaggio di inserimento del valore mentre nel caso peggiore avremmo 2N+1 passaggi per N elementi poichè nel caso peggiore dovremmo inserire gli elementi all'inizio del set e quindi dovremmo effettuare N ricerche per N valori per assicurarci che non ci siano doppioni, N spostamenti verso destra e poi un passaggio per inserire effettivamente l'elemento se non contenuto.

Eliminazione:

L’eliminazione consiste nella cancellazione di un valore situato a un determinato indice, anche se tecnicamente l’eliminazione richiederebbe un solo passaggio poichè si elimina tramite indice, in realtà ci riscontriamo un problema cioè che abbiamo uno spazio vuoto nell’array e ovviamente l’array non deve avere spazi vuoti quindi dovremmo fare altri passaggi in modo spostare lo spazio bianco alla fine e quindi a livello di efficienza avremmo che si faranno una eliminazione e poi N spostamenti nel caso peggiore e invece solo una eliminazione nel caso migliore.